﻿#include <iostream>
using namespace std;
//
节点类型声明

struct Node
{
	int data;
	Node* next;
};
struct List
{
	//
	指向头节点的指针

		Node* phead;
	//
	成员函数

		//
		构造函数

		List()
	{
		cout << "
			构造函数调⽤
			" << endl;
			phead = nullptr;
	}
	//
	析构函数
		-
		在结束时释放所有剩余节点

		~List()
	{
		cout << "
			析构函数
			" << endl;
			while (phead)
			{
				PopFront();
			}
	}
	//
	创建节点

		Node* createNode(int data)
	{
		Node* newNode = new Node;
		newNode->data = data;
        newNode->next = nullptr;
        return newNode;
    }
    //
    打印链表

        void printList()
    {
        Node* cur = phead;
        while (cur != nullptr)
        {
            cout << cur->data << "-->";
            cur = cur->next;
        }
        cout << "nullptr" << endl;
        cout << endl;
    }
    //
    头部添加元素

        void PushFront(int data)
    {
        Node* newNode = createNode(data);
        newNode->next = phead;
        phead = newNode;
    }
    //
    头部删除元素

        void PopFront()
    {
        // 
        空

            if (phead == nullptr)
            {
                cout << "
                    链表为空，没有元素可以删除了
                    " << endl;
                    return;
            }
        //
        ⾮空

            Node* tmp = phead;
        phead = phead->next;
        delete tmp;
        tmp = nullptr;
    }
    //
    尾部添加元素

        void PushBack(int x)
    {
        Node* newnode = createNode(x);
        // 1
        、空链表
            // 2
            、⾮空链表

            if (phead == nullptr)
            {
                phead = newnode;
            }
            else
            {
                Node* tail = phead;
                while (tail->next != nullptr)
                {
                    tail = tail->next;
                }
                tail->next = newnode;
            }
    }
    //
    尾部删除元素

        void PopBack()
    {
        //
        空链表

            if (phead == nullptr)
            {
                cout << "
                    链表为空，没有元素可以删除了
                    " << endl;
                    return;
            }
        // 1
        、⼀个节点

            // 2
            、⼀个以上节点

            if ((phead)->next == nullptr)
            {
                delete phead;
                phead = nullptr;
            }
            else
            {
                // 
                找尾

                    Node* tail = phead;
                while (tail->next->next != nullptr)
                {
                    tail = tail->next;
                }
                delete tail->next;
                tail->next = nullptr;
            }
    }
    void DestropList()
    {
        while (phead)
        {
            PopFront();
        }
    }
 };
 int main()
 {
     List list;
     list.PushBack(1);
     list.PushBack(2);
     list.PushBack(3);
     list.PushBack(4);
     list.printList();
     //
     头部删除并打印

         list.PopBack();
     list.printList();
     list.PopBack();
     list.printList();
     list.PopBack();
     list.printList();
     list.PopBack();
     list.printList();
     list.PopBack();
     list.printList();
     //
     头部添加元素

         list.PushFront(1);
     list.PushFront(2);
     list.PushFront(3);
     list.PushFront(4);
     list.printList();
     //
     头部删除

         list.PopFront();
     list.printList();
     list.PopFront();
     list.printList();
     return 0;
 }
//#include <iostream>
//using namespace std;
//struct Node
//{
//	int data;
//	Node* next;
//};
//Node* createNode(int data)
//{
//	Node* newNode = new Node;
//	newNode->data = data;
//	newNode->next = nullptr;
//	return newNode;
//}
//void printList(Node* cur)
//{
//	while (cur != nullptr)
//	{
//		cout << cur->data << "-->";
//		cur = cur->next;
//	}
//	cout << "nullptr" << endl;
//	cout << endl;
//}
//void PushBack(Node*& phead, int x)
//{
//	Node* newnode = createNode(x);
//	// 1
//	、空链表
//
//		// 2
//		、⾮空链表
//
//		if (phead == nullptr)
//		{
//			phead = newnode;
//		}
//		else
//		{
//			Node* tail = phead;
//			while (tail->next != nullptr)
//			{
//				tail = tail->next;
//			}
//			tail->next = newnode;
//		}
//}
//void PopFront(Node*& ph)
//{
//	// 
//	空
//
//		if (ph == nullptr)
//		{
//			cout << "
//				链表为空，没有元素可以删除了
//				" << endl;
//				return;
//		}
//	//
//	⾮空
//
//		Node* tmp = ph;
//	ph = ph->next;
//	delete tmp;
//	tmp = nullptr;
//}
//void DestropList(Node*& ph)
//{
//	while (ph)
//	{
//		PopFront(ph);
//	}
//}
//int main()
//{
//	Node* phead = nullptr;
//	PushBack(phead, 1);
//	PushBack(phead, 2);
//	PushBack(phead, 3);
//	PushBack(phead, 4);
//	printList(phead);
//	//
//	释放链表
//
//		DestroyList(phead);
//	return 0;
//}
//void PopFront(Node*& ph)
//{
//	// 
//	空
//
//		if (ph == nullptr)
//		{
//			cout << "
//				链表为空，没有元素可以删除了
//				" << endl;
//				return;
//		}
//	//
//	⾮空
//
//		Node* tmp = ph;
//	ph = ph->next;
//	delete tmp;
//	tmp = nullptr;
//}
//void DestropList(Node*& ph)
//{
//	while (ph)
//	{
//		PopFront(ph);
//	}
//}
//#include <iostream>
//using namespace std;
//struct Node
//{
//	int data;
//	Node* next;
//};
//Node* createNode(int data)
//{
//	Node* newNode = new Node;
//	newNode->data = data;
//	newNode->next = nullptr;
//	return newNode;
//}
//void printList(Node* cur)
//{
//	while (cur != nullptr)
//	{
//		cout << cur->data << "-->";
//		cur = cur->next;
//	}
//	cout << "nullptr" << endl;
//	cout << endl;
//}
//void PushBack(Node*& phead, int x)
//{
//	Node* newnode = createNode(x);
//	// 1
//	、空链表
//
//		// 2
//		、⾮空链表
//
//		if (phead == nullptr)
//		{
//			phead = newnode;
//		}
//		else
//		{
//			Node* tail = phead;
//            while (tail->next != nullptr)
//            {
//                tail = tail->next;
//            }
//            tail->next = newnode;
//        }
//}
//void PopBack(Node*& phead)
//{
//    //
//    空链表
//
//        if (phead == nullptr)
//        {
//            cout << "
//                链表为空，没有元素可以删除了
//                " << endl;
//                return;
//        }
//    // 1
//    、⼀个节点
//
//        // 2
//        、⼀个以上节点
//
//        if ((phead)->next == nullptr)
//        {
//            delete phead;
//            phead = nullptr;
//        }
//        else
//        {
//            // 
//            找尾
//
//                Node* tail = phead;
//            while (tail->next->next != nullptr)
//            {
//                tail = tail->next;
//            }
//            delete tail->next;
//            tail->next = nullptr;
//        }
//}
//int main()
//{
//    Node* phead = nullptr;
//    PushBack(phead, 1);
//    PushBack(phead, 2);
//    PushBack(phead, 3);
//    PushBack(phead, 4);
//    printList(phead);
//    //
//    头部删除并打印
//
//        PopBack(phead);
//    printList(phead);
//    PopBack(phead);
//    printList(phead);
//    PopBack(phead);
//    printList(phead);
//    PopBack(phead);
//    printList(phead);
//    PopBack(phead);
//    printList(phead);
//    return 0;
//}
//void PopBack(Node*& phead)
//{
//    //空链表
//
//        if (phead == nullptr)
//        {
//            cout << "链表为空，没有元素可以删除了" << endl;
//            return;
//        }
//    //1、⼀个节点
//    //2、⼀个以上节点
//
//        if (phead->next == nullptr)
//        {
//            free(phead);
//            phead = nullptr;
//        }
//        else
//        {
//            //找尾
//            Node* tail = phead;
//            while (tail->next->next != nullptr)
//            {
//                tail = tail->next;
//            }
//            free(tail->next);
//            tail->next = nullptr;
//        }
//}
//#include <iostream>
//using namespace std;
//struct Node
//{
//	int data;
//	Node* next;
//};
//Node* createNode(int data)
//{
//	Node* newNode = new Node;
//	newNode->data = data;
//	newNode->next = nullptr;
//	return newNode;
//}
//void printList(Node* cur)
//{
//	while (cur != nullptr)
//	{
//		cout << cur->data << "-->";
//		cur = cur->next;
//	}
//	cout << "nullptr" << endl;
//	cout << endl;
//}
//void PushBack(Node*& phead, int x)
//{
//    Node* newnode = createNode(x);
//    // 1
//    、空链表
//
//        // 2
//        、⾮空链表
//
//        if (phead == nullptr)
//        {
//            phead = newnode;
//        }
//        else
//        {
//            Node* tail = phead;
//            while (tail->next != nullptr)
//            {
//                tail = tail->next;
//            }
//            tail->next = newnode;
//        }
//}
//void PopFront(Node*& phead)
//{
//    //空
//
//        if (phead == nullptr)
//        {
//            cout << "链表为空，没有元素可以删除了" << endl;
//            return;
//        }
//    //非空
//    Node* tmp = phead;
//    phead = phead->next;
//    delete tmp;
//    tmp = nullptr;
//}
//int main()
//{
//    Node* phead = nullptr;
//    PushBack(phead, 1);
//    PushBack(phead, 2);
//    PushBack(phead, 3);
//    PushBack(phead, 4);
//    printList(phead);
//    //头部删除并打印
//    PopFront(phead);
//    printList(phead);
//    PopFront(phead);
//    printList(phead);
//    PopFront(phead);
//    printList(phead);
//    PopFront(phead);
//    printList(phead);
//    PopFront(phead);
//    printList(phead);
//    return 0;
//}
//void PopFront(Node*& phead)
//{
//	//空
//	if (phead == nullptr)
//	{
//		cout << "链表为空，没有元素可以删除了" << endl;
//		return;
//	}
//	//非空
//	Node* tmp = phead;
//	phead = phead->next;
//	delete tmp;
//	tmp = nullptr;
//}
//#include <iostream>
//using namespace std;
//struct Node
//{
//	int data;
//	Node* next;
//};
//Node* createNode(int data)
//{
//	Node* newNode = new Node;
//	newNode->data = data;
//	newNode->next = nullptr;
//	return newNode;
//}
//void printList(Node* cur)
//{
//	while (cur != nullptr)
//	{
//		cout << cur->data << "-->";
//		cur = cur->next;
//	}
//	cout << "nullptr" << endl;
//	cout << endl;
//}
//
//void PushBack(Node * &phead, int x)
//{
//	Node* newnode = createNode(x);
//	// 1、空链表
//	// 2、非空链表
//
//		if (phead == nullptr)
//		{
//			phead = newnode;
//		}
//		else
//		{
//			Node* tail = phead;
//			while (tail->next != nullptr)
//			{
//				tail = tail->next;
//			}
//			tail->next = newnode;
//		}
//}
//int main()
//{
//	Node* phead = nullptr;
//	PushBack(phead, 1);
//	PushBack(phead, 2);
//	PushBack(phead, 3);
//	PushBack(phead, 4);
//	printList(phead);
//	return 0;
//}
//void PushBack(Node*& phead, int x)
//{
//	Node* newnode = createNode(x);
//	// 1、空链表
//	// 2、非空链表
//
//		if (phead == nullptr)
//		{
//			phead = newnode;
//		}
//		else
//		{
//			Node* tail = phead;
//			while (tail->next != nullptr)
//			{
//				tail = tail->next;
//			}
//			tail->next = newnode;
//		}
//}
//#include <iostream>
//using namespace std;
//struct Node
//{
//    int data;
//    Node* next;
//};
//Node* createNode(int data)
//{
//    Node* newNode = new Node;
//    newNode->data = data;
//    newNode->next = nullptr;
//    return newNode;
//}
//void printList(Node* cur)
//{
//    while (cur != nullptr)
//    {
//        cout << cur->data << "-->";
//        cur = cur->next;
//    }
//    cout << "nullptr" << endl;
//    cout << endl;
//}
//void PushFront(Node*& ph, int data)
//{
//    Node* newNode = createNode(data);
//    newNode->next = ph;
//    ph = newNode;
//}
//int main()
//{
//    Node* phead = nullptr;
//    PushFront(phead, 1);
//    PushFront(phead, 2);
//    PushFront(phead, 3);
//    PushFront(phead, 4);
//    printList(phead);
//    return 0;
//}
////#include <iostream>
////using namespace std;
////struct Node
////{
////	int data;
////	Node* next;
////};
////Node* createNode(int data)
////{
////	Node* newNode = new Node;
////	newNode->data = data;
////	newNode->next = nullptr;
////	return newNode;
////}
////void printList(Node * cur)
////{
////	while (cur != nullptr)
////	{
////		cout << cur->data << "-->";
////		cur = cur->next;
////	}
////	cout << "nullptr" << endl;
////	cout << endl;
////}
////void PushFront(Node * &ph, int data)
////{
////	Node* newNode = createNode(data);
////	newNode->next = pn;
////	ph = newNode;
////}
////int main()
////{
////	Node* phead = nullptr;
////	PushFront(phead, 1);
////	PushFront(phead, 2);
////	PushFront(phead, 3);
////	PushFront(phead, 4);
////	printList(phead);
////	return 0;
////}
//////void PushFront(Node*& ph, int data)
//////{
//////	Node* newNode = createNode(data);
//////	newNode->next = ph;
//////	ph = newNode;
//////}
//////#include <iostream>
//////using namespace std;
//////struct Node
//////{
//////	int data;
//////	Node* next;
//////};
//////Node* createNode(int data)
//////{
//////	Node* newNode = new Node;
//////	newNode->data = data;
//////	newNode->next = nullptr;
//////	return newNode;
//////}
//////void printList(Node* cur)
//////{
//////	while (cur != nullptr)
//////	{
//////		cout << cur->data << "-->";
//////		cur = cur->next;
//////	}
//////	cout << "nullptr" << endl;
//////	cout << endl;
//////}
//////int main()
//////{
//////	Node* p1 = createNode(1);
//////	Node* p2 = createNode(2);
//////	Node* p3 = createNode(3);
//////	Node* p4 = createNode(4);
//////	p1->next = p2;
//////	p2->next = p3;
//////	p3->next = p4;
//////	printList(p1);
//////	return 0;
//////}
//////void printList(Node* cur)
//////{
//////	while (cur != nullptr)
//////	{
//////		cout << cur->data << "-->";
//////		cur = cur->next;
//////	}
//////	cout << "nullptr" << endl;
//////	cout << endl;
//////}
//////Node* createNode(int data)
//////{
//////	Node* newNode = new Node;
//////	newNode->data = data;
//////	newNode->next = nullptr;
//////	return newNode;
//////}
//////////链表节点类型的声明
////////struct Node
////////{
////////	int data;
////////	Node* next;
////////};